package leetcode.editor.cn;

//给定一个二叉树，找出其最小深度。 
//
// 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 
//
// 说明: 叶子节点是指没有子节点的节点。 
//
// 示例: 
//
// 给定二叉树 [3,9,20,null,null,15,7], 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7 
//
// 返回它的最小深度 2. 
// Related Topics 树 深度优先搜索 广度优先搜索

import lombok.Data;

import java.util.LinkedList;
import java.util.Queue;

public class MinimumDepthOfBinaryTree{
    public static void main(String[] args) {
        Solution solution = new MinimumDepthOfBinaryTree().new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(solution.minDepth(root));
    }

    @Data
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 *
 * // 给定二叉树 [3,9,20,null,null,15,7],
 * //
 * //     3
 * //   / \
 * //  9  20
 * //    /  \
 * //   15   7
 */
class Solution {
//    public int minDepth(TreeNode root) {
//        if(root == null) return 0;
//        //这道题递归条件里分为三种情况
//        //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
//        if(root.left == null && root.right == null) return 1;
//        //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度
//        int m1 = minDepth(root.left);
//        int m2 = minDepth(root.right);
//        //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
////        if(root.left == null || root.right == null) return m1 + m2 + 1;
//        if(root.left == null) return m2+1;
//        if(root.right == null) return m1+1;
//
//        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
//        return Math.min(m1,m2) + 1;
//    }

    /*
        广度优先遍历，找到叶子节点则直接返回深度
     */
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null) return depth;
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}